package com.mlh.graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

//图的广度优先遍历
public class BFS {
    public static void BreadthFirstSeach(Node node){
        if(node==null){
            return;
        }
        //针对无向图
        //利用队列来实现
        Queue<Node> queue=new LinkedList<>();
        HashSet<Node> set=new HashSet<>();
        //先将第一个节点入队
        System.out.println(node.value);
        queue.add(node);
        set.add(node);
        //遍历出队节点的所有相邻节点
        //对于没有被访问过的节点  打印 进入队列  放入到set中
        //有没有被访问过利用hashset来实现
        //以上操作为循环 退出循环的条件是队列为空
        while (!queue.isEmpty()){
           Node temp=queue.poll();
           for(Node next:temp.nexts){
               if(!set.contains(next)){
                   set.add(next);
                   System.out.println(next.value);
                   queue.add(next);
               }
           }
        }
    }
}
